{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Operations to Make the Array Alternating"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumOperations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使数组变成交替数组的最少操作数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的数组 <code>nums</code> ，该数组由 <code>n</code> 个正整数组成。</p>\n",
    "\n",
    "<p>如果满足下述条件，则数组 <code>nums</code> 是一个 <strong>交替数组</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums[i - 2] == nums[i]</code> ，其中 <code>2 &lt;= i &lt;= n - 1</code> 。</li>\n",
    "\t<li><code>nums[i - 1] != nums[i]</code> ，其中 <code>1 &lt;= i &lt;= n - 1</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>在一步 <strong>操作</strong> 中，你可以选择下标 <code>i</code> 并将 <code>nums[i]</code> <strong>更改</strong> 为 <strong>任一</strong> 正整数。</p>\n",
    "\n",
    "<p>返回使数组变成交替数组的 <strong>最少操作数</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,1,3,2,4,3]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "使数组变成交替数组的方法之一是将该数组转换为 [3,1,3,<em><strong>1</strong></em>,<em><strong>3</strong></em>,<em><strong>1</strong></em>] 。\n",
    "在这种情况下，操作数为 3 。\n",
    "可以证明，操作数少于 3 的情况下，无法使数组变成交替数组。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,2,2,2]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "使数组变成交替数组的方法之一是将该数组转换为 [1,2,<em><strong>1</strong></em>,2,<em><strong>1</strong></em>].\n",
    "在这种情况下，操作数为 2 。\n",
    "注意，数组不能转换成 [<em><strong>2</strong></em>,2,2,2,2] 。因为在这种情况下，nums[0] == nums[1]，不满足交替数组的条件。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-operations-to-make-the-array-alternating](https://leetcode.cn/problems/minimum-operations-to-make-the-array-alternating/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-operations-to-make-the-array-alternating](https://leetcode.cn/problems/minimum-operations-to-make-the-array-alternating/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,1,3,2,4,3]', '[1,2,2,2,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "\n",
    "        def check(k):\n",
    "            counter = collections.defaultdict(int)\n",
    "            cnt = 0\n",
    "            for i in range(k, len(nums), 2):\n",
    "                cnt += 1\n",
    "                counter[nums[i]] += 1\n",
    "                \n",
    "            m, sm = [0, 0], [0, 0]\n",
    "            for k, v in counter.items():\n",
    "                if v > m[1]:\n",
    "                    m, sm = [k, v], m \n",
    "                elif v == m[1]:\n",
    "                    sm = [k, v]\n",
    "                elif v > sm[1]:\n",
    "                    sm = [k, v]\n",
    "            return m, sm, cnt\n",
    "        \n",
    "        om, osm, ocnt = check(0)\n",
    "        em, esm, ecnt = check(1)\n",
    "        \n",
    "        if om[0] != em[0]:\n",
    "            return len(nums)-om[1]-em[1]\n",
    "        return min(ocnt-om[1] + ecnt-esm[1], ocnt-osm[1] + ecnt - em[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        if l == 1:\n",
    "            return 0\n",
    "        n0 = Counter(nums[::2]).most_common(2)\n",
    "        n1 = Counter(nums[1::2]).most_common(2)\n",
    "        if len(n0) == 1:\n",
    "            n0.append((0, 0))\n",
    "        if len(n1) == 1:\n",
    "            n1.append((0, 0))\n",
    "        if n0[0][0] != n1[0][0]:\n",
    "            return l - n0[0][1] - n1[0][1]\n",
    "        else:\n",
    "            return l - max(n0[1][1] + n1[0][1], n0[0][1] + n1[1][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0  \n",
    "\t\t# 奇偶统计 分别得到出现次数最多和次多的元素及其对应频次\n",
    "        cnt0 = Counter(nums[::2]).most_common(2)   # 偶数组统计：下标0开始，间隔为2\n",
    "        cnt1 = Counter(nums[1::2]).most_common(2)  # 奇数组统计：下标1开始，间隔为2\n",
    "\n",
    "        if cnt0[0][0] != cnt1[0][0]:    # 两个数组中，出现次数最多的元素不同\n",
    "            return n-cnt0[0][1]-cnt1[0][1]\n",
    "        else:                           # 两个数组中，出现次数最多的元素相同\n",
    "            cost0 = n - cnt0[0][1] - (0 if len(cnt1)==1 else cnt1[1][1])    # 保留偶数组中出现次数最多的元素，并考虑保留奇数组中出现次数第二多（如存在）的元素\n",
    "            cost1 = n - cnt1[0][1] - (0 if len(cnt0)==1 else cnt0[1][1])    # 保留奇数组中出现次数最多的元素，并考虑保留偶数组中出现次数第二多（如存在）的元素\n",
    "\n",
    "            return min(cost0, cost1)    # 两种情况取最小值\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        # start = 0 表示偶数下标，start = 1 表示奇数下标\n",
    "        # 返回值为最大键，最大键对应的值，次大键，次大键对应的值\n",
    "        def get(start: int) -> Tuple[int, int, int, int]:\n",
    "            freq = Counter(nums[start::2]) #分别计算一下奇数和偶数\n",
    "            best = freq.most_common(2)#找到最大和次大\n",
    "            if not best:\n",
    "                return (0, 0, 0, 0)\n",
    "            if len(best) == 1:\n",
    "                return *best[0], *(0, 0)\n",
    "            \n",
    "            return *best[0], *best[1]\n",
    "            \n",
    "        e1stkey, e1stval, e2ndkey, e2ndval = get(0)\n",
    "        o1stkey, o1stval, o2ndkey, o2ndval = get(1)\n",
    "\n",
    "        if e1stkey != o1stkey:\n",
    "            return n - (e1stval + o1stval)\n",
    "        \n",
    "        return n - max(e1stval + o2ndval, o1stval + e2ndval)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        # start = 0 表示偶数下标，start = 1 表示奇数下标\n",
    "        # 返回值为最大键，最大键对应的值，次大键，次大键对应的值\n",
    "        def get(start: int) -> Tuple[int, int, int, int]:\n",
    "            freq = Counter(nums[start::2])\n",
    "            best = freq.most_common(2)\n",
    "            if not best:\n",
    "                return 0, 0, 0, 0\n",
    "            if len(best) == 1:\n",
    "                return *best[0], 0, 0\n",
    "            \n",
    "            return *best[0], *best[1]\n",
    "            \n",
    "        e1stkey, e1stval, e2ndkey, e2ndval = get(0)\n",
    "        o1stkey, o1stval, o2ndkey, o2ndval = get(1)\n",
    "\n",
    "        if e1stkey != o1stkey:\n",
    "            return n - (e1stval + o1stval)\n",
    "        \n",
    "        return n - max(e1stval + o2ndval, o1stval + e2ndval)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        def get(start):\n",
    "            freq = Counter(nums[start::2])\n",
    "            best = freq.most_common(2)\n",
    "            if not best:\n",
    "                return 0, 0, 0, 0\n",
    "            if len(best) == 1:\n",
    "                return *best[0], 0, 0\n",
    "            return *best[0], *best[1]\n",
    "\n",
    "        e1k, e1v, e2k, e2v = get(0)\n",
    "        o1k, o1v, o2k, o2v = get(1)\n",
    "\n",
    "        if (e1k != o1k): return n - e1v - o1v\n",
    "        return n - max(e1v + o2v, e2v + o1v)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        # start = 0 表示偶数下标，start = 1 表示奇数下标\n",
    "        # 返回值为最大键，最大键对应的值，次大键，次大键对应的值\n",
    "        def get(start: int) -> Tuple[int, int, int, int]:\n",
    "            freq = Counter(nums[start::2])\n",
    "            best = freq.most_common(2)\n",
    "            if not best:\n",
    "                return (0, 0, 0, 0)\n",
    "            if len(best) == 1:\n",
    "                return (*best[0], 0, 0)\n",
    "            \n",
    "            return *best[0], *best[1]\n",
    "            \n",
    "        e1stkey, e1stval, e2ndkey, e2ndval = get(0)\n",
    "        o1stkey, o1stval, o2ndkey, o2ndval = get(1)\n",
    "\n",
    "        if e1stkey != o1stkey:\n",
    "            return n - (e1stval + o1stval)\n",
    "        \n",
    "        return n - max(e1stval + o2ndval, o1stval + e2ndval)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        odd = Counter(nums[1::2]).most_common(2)+[(0,0)]\n",
    "        even = Counter(nums[0::2]).most_common(2)+[(0,0)]\n",
    "        \n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        if odd[0][0]!=even[0][0]:\n",
    "            ans = n-odd[0][1]-even[0][1]\n",
    "        else:\n",
    "            ans = n-max(odd[0][1]+even[1][1], odd[1][1]+even[0][1])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        # start = 0 表示偶数下标，start = 1 表示奇数下标\n",
    "        # 返回值为最大键，最大键对应的值，次大键，次大键对应的值\n",
    "        def get(start: int) -> Tuple[int, int, int, int]:\n",
    "            freq = Counter(nums[start::2])\n",
    "            best = freq.most_common(2)\n",
    "            if not best:\n",
    "                return (0, 0, 0, 0)\n",
    "            if len(best) == 1:\n",
    "                return *best[0], 0, 0\n",
    "            \n",
    "            return *best[0], *best[1]\n",
    "            \n",
    "        e1stkey, e1stval, e2ndkey, e2ndval = get(0)\n",
    "        o1stkey, o1stval, o2ndkey, o2ndval = get(1)\n",
    "\n",
    "        if e1stkey != o1stkey:\n",
    "            return n - (e1stval + o1stval)\n",
    "        \n",
    "        return n - max(e1stval + o2ndval, o1stval + e2ndval)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        # start = 0 表示偶数下标，start = 1 表示奇数下标\n",
    "        # 返回值为最大键，最大键对应的值，次大键，次大键对应的值\n",
    "        def get(start: int) -> Tuple[int, int, int, int]:\n",
    "            freq = Counter(nums[start::2])\n",
    "            best = freq.most_common(2)\n",
    "            if not best:\n",
    "                return 0, 0, 0, 0\n",
    "            if len(best) == 1:\n",
    "                return *best[0], 0, 0\n",
    "            \n",
    "            return *best[0], *best[1]\n",
    "            \n",
    "        e1stkey, e1stval, e2ndkey, e2ndval = get(0)\n",
    "        o1stkey, o1stval, o2ndkey, o2ndval = get(1)\n",
    "\n",
    "        if e1stkey != o1stkey:\n",
    "            return n - (e1stval + o1stval)\n",
    "        \n",
    "        return n - max(e1stval + o2ndval, o1stval + e2ndval)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        # start = 0 表示偶数下标，start = 1 表示奇数下标\n",
    "        # 返回值为最大键，最大键对应的值，次大键，次大键对应的值\n",
    "        def get(start: int) -> Tuple[int, int, int, int]:\n",
    "            freq = Counter(nums[start::2])\n",
    "            best = freq.most_common(2)\n",
    "            if not best:\n",
    "                return 0, 0, 0, 0\n",
    "            if len(best) == 1:\n",
    "                return *best[0], 0, 0\n",
    "            \n",
    "            return *best[0], *best[1]\n",
    "            \n",
    "        e1stkey, e1stval, e2ndkey, e2ndval = get(0)\n",
    "        o1stkey, o1stval, o2ndkey, o2ndval = get(1)\n",
    "\n",
    "        if e1stkey != o1stkey:\n",
    "            return n - (e1stval + o1stval)\n",
    "        \n",
    "        return n - max(e1stval + o2ndval, o1stval + e2ndval)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        # start = 0 表示偶数下标，start = 1 表示奇数下标\n",
    "        # 返回值为最大键，最大键对应的值，次大键，次大键对应的值\n",
    "        def get(start: int) -> Tuple[int, int, int, int]:\n",
    "            freq = Counter(nums[start::2])\n",
    "            best = freq.most_common(2)\n",
    "            if not best:\n",
    "                return (0, 0), (0, 0)\n",
    "            if len(best) == 1:\n",
    "                return best[0], (0, 0)\n",
    "            return best[0], best[1]      \n",
    "        (e1stkey, e1stval), (e2ndkey, e2ndval) = get(0)\n",
    "        (o1stkey, o1stval), (o2ndkey, o2ndval) = get(1)\n",
    "\n",
    "        if e1stkey != o1stkey:\n",
    "            return n - (e1stval + o1stval)\n",
    "        \n",
    "        return n - max(e1stval + o2ndval, o1stval + e2ndval)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        cnt0 = Counter(nums[::2]).most_common(2)  \n",
    "        cnt1 = Counter(nums[1::2]).most_common(2) \n",
    "        if cnt0[0][0] != cnt1[0][0]:   \n",
    "            return n-cnt0[0][1]-cnt1[0][1]\n",
    "        else:                          \n",
    "            cost0 = n - cnt0[0][1] - (0 if len(cnt1)==1 else cnt1[1][1])    \n",
    "            cost1 = n - cnt1[0][1] - (0 if len(cnt0)==1 else cnt0[1][1])    \n",
    "            return min(cost0, cost1)   \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        \n",
    "        cnt0 = Counter(nums[::2]).most_common(2)\n",
    "        cnt1 = Counter(nums[1::2]).most_common(2)\n",
    "\n",
    "\n",
    "        if cnt0[0][0] != cnt1[0][0]:\n",
    "            return n - cnt0[0][1] - cnt1[0][1]\n",
    "        else:\n",
    "            cost0 = n - cnt0[0][1] - (0 if len(cnt1) == 1 else cnt1[1][1])\n",
    "            cost1 = n - cnt1[0][1] - (0 if len(cnt0) == 1 else cnt0[1][1])\n",
    "            return min(cost0, cost1)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        \n",
    "\t\t# 奇偶统计 分别得到出现次数最多和次多的元素及其对应频次\n",
    "        cnt0 = Counter(nums[::2]).most_common(2)   # 偶数组统计：下标0开始，间隔为2\n",
    "        cnt1 = Counter(nums[1::2]).most_common(2)  # 奇数组统计：下标1开始，间隔为2\n",
    "\n",
    "        if cnt0[0][0] != cnt1[0][0]:    # 两个数组中，出现次数最多的元素不同\n",
    "            return n-cnt0[0][1]-cnt1[0][1]\n",
    "        else:                           # 两个数组中，出现次数最多的元素相同\n",
    "            cost0 = n - cnt0[0][1] - (0 if len(cnt1)==1 else cnt1[1][1])    # 保留偶数组中出现次数最多的元素，并考虑保留奇数组中出现次数第二多（如存在）的元素\n",
    "            cost1 = n - cnt1[0][1] - (0 if len(cnt0)==1 else cnt0[1][1])    # 保留奇数组中出现次数最多的元素，并考虑保留偶数组中出现次数第二多（如存在）的元素\n",
    "\n",
    "            return min(cost0, cost1)    # 两种情况取最小值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        def get(start: int) -> Tuple[int, int, int, int]:\n",
    "            freq = Counter(nums[start::2])\n",
    "            best = freq.most_common(2)\n",
    "            if not best:\n",
    "                return 0, 0, 0, 0\n",
    "            if len(best) == 1:\n",
    "                return *best[0], 0, 0\n",
    "            \n",
    "            return *best[0], *best[1]\n",
    "\n",
    "        e1stkey, e1stval, e2ndkey, e2ndval = get(0)\n",
    "        o1stkey, o1stval, o2ndkey, o2ndval = get(1)\n",
    "\n",
    "        if e1stkey != o1stkey:\n",
    "            return n - (e1stval + o1stval)\n",
    "        \n",
    "        return n - max(e1stval + o2ndval, o1stval + e2ndval)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        def get(start):\n",
    "            freq = Counter(nums[start::2])\n",
    "            best = freq.most_common(2)\n",
    "            if not best:\n",
    "                return 0, 0, 0, 0\n",
    "            if len(best) == 1:\n",
    "                return *best[0], 0, 0\n",
    "            return *best[0], *best[1]\n",
    "\n",
    "        e1k, e1v, e2k, e2v = get(0)\n",
    "        o1k, o1v, o2k, o2v = get(1)\n",
    "        if (e1k != o1k):\n",
    "            return n - e1v - o1v;\n",
    "        \n",
    "        return n - max(e1v + o2v, e2v + o1v);\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:\n",
    "            return 0\n",
    "        nums1,nums2=nums[::2],nums[1::2]\n",
    "        list1=Counter(nums1).most_common(2)\n",
    "        list2=Counter(nums2).most_common(2)\n",
    "        print(list1)\n",
    "        print(list2)\n",
    "        if list1[0][0]!=list2[0][0]:\n",
    "            return len(nums)-list1[0][1]-list2[0][1]\n",
    "        else:\n",
    "            a=len(nums)-list2[0][1]-(list1[1][1] if len(list1)==2 else 0)\n",
    "            b=len(nums)-list1[0][1]-(list2[1][1] if len(list2)==2 else 0)\n",
    "            return min(a,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 2: return 0\n",
    "\n",
    "        cnt_x = Counter(nums[::2])\n",
    "        cnt_y = Counter(nums[1::2])\n",
    "        \n",
    "        x0, x1, cntx0, cntx1 = -1,-1,0,0\n",
    "        y0, y1, cnty0, cnty1 = -1,-1,0,0\n",
    "        \n",
    "        for k, v in cnt_x.items():\n",
    "            if v > cntx1:\n",
    "                cntx0 = cntx1\n",
    "                x0 = x1\n",
    "                \n",
    "                cntx1 = v\n",
    "                x1 = k\n",
    "\n",
    "            elif v > cntx0:\n",
    "                cntx0 = v\n",
    "                x0 = k\n",
    "        \n",
    "        for k, v in cnt_y.items():\n",
    "            if v > cnty1:\n",
    "                cnty0 = cnty1\n",
    "                y0 = y1\n",
    "                \n",
    "                cnty1 = v\n",
    "                y1 = k\n",
    "\n",
    "            elif v > cnty0:\n",
    "                cnty0 = v\n",
    "                y0 = k\n",
    "        \n",
    "        sx = sum(cnt_x.values())\n",
    "        sy = sum(cnt_y.values())\n",
    "        \n",
    "        if x1 != y1:\n",
    "            return sx - cntx1 + sy - cnty1\n",
    "\n",
    "        return sx + sy - max(cntx0 + cnty1, cntx1 + cnty0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:return 0\n",
    "        c1, c2 = Counter(nums[::2]), Counter(nums[1::2])\n",
    "        max1, max2 = c1.most_common(2), c2.most_common(2)\n",
    "        if max1[0][0] == max2[0][0]:\n",
    "            if len(max1)==1: max1.append((0,0))\n",
    "            if len(max2)==1: max2.append((0,0))\n",
    "            return min(len(nums) - max1[1][1]-max2[0][1], len(nums) - max1[0][1]-max2[1][1])\n",
    "        return len(nums) - max1[0][1]-max2[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        numDict1 = collections.defaultdict(int)\n",
    "        oddFst = oddSnd = -1\n",
    "        for i in range(0, n, 2):\n",
    "            numDict1[nums[i]] += 1\n",
    "            if numDict1[nums[i]] > numDict1[oddFst]:\n",
    "                oddFst, oddSnd = nums[i], oddFst\n",
    "            elif numDict1[oddFst] == numDict1[nums[i]]: \n",
    "                if oddFst != nums[i]:\n",
    "                    oddSnd = nums[i] \n",
    "            elif numDict1[nums[i]] > numDict1[oddSnd]:\n",
    "                oddSnd = nums[i] \n",
    "\n",
    "        numDict2 = collections.defaultdict(int)\n",
    "        evenFst = evenSnd = -1\n",
    "        for i in range(1, n, 2):\n",
    "            numDict2[nums[i]] += 1\n",
    "            if numDict2[nums[i]] > numDict2[evenFst]:\n",
    "                evenFst, evenSnd = nums[i], evenFst\n",
    "            elif numDict2[evenFst] == numDict2[nums[i]]: \n",
    "                if evenFst != nums[i]:\n",
    "                    evenSnd = nums[i] \n",
    "            elif numDict2[nums[i]] > numDict2[evenSnd]:\n",
    "                evenSnd = nums[i] \n",
    "\n",
    "        if oddFst != evenFst:\n",
    "            return n - numDict1[oddFst] - numDict2[evenFst]\n",
    "        else:\n",
    "            return n - max(numDict1[oddFst] + numDict2[evenSnd], numDict1[oddSnd] + numDict2[evenFst])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        numDict1 = collections.defaultdict(int)\n",
    "        oddFst = oddSnd = -1\n",
    "        for i in range(0, n, 2):\n",
    "            numDict1[nums[i]] += 1\n",
    "            if numDict1[nums[i]] > numDict1[oddFst]:\n",
    "                oddFst, oddSnd = nums[i], oddFst\n",
    "            elif numDict1[oddFst] == numDict1[nums[i]]: \n",
    "                if oddFst != nums[i]:\n",
    "                    oddSnd = nums[i] \n",
    "            elif numDict1[nums[i]] > numDict1[oddSnd]:\n",
    "                oddSnd = nums[i] \n",
    "\n",
    "        numDict2 = collections.defaultdict(int)\n",
    "        evenFst = evenSnd = -1\n",
    "        for i in range(1, n, 2):\n",
    "            numDict2[nums[i]] += 1\n",
    "            if numDict2[nums[i]] > numDict2[evenFst]:\n",
    "                evenFst, evenSnd = nums[i], evenFst\n",
    "            elif numDict2[evenFst] == numDict2[nums[i]]: \n",
    "                if evenFst != nums[i]:\n",
    "                    evenSnd = nums[i] \n",
    "            elif numDict2[nums[i]] > numDict2[evenSnd]:\n",
    "                evenSnd = nums[i] \n",
    "\n",
    "        if oddFst != evenFst:\n",
    "            return n - numDict1[oddFst] - numDict2[evenFst]\n",
    "        else:\n",
    "            return n - max(numDict1[oddFst] + numDict2[evenSnd], numDict1[oddSnd] + numDict2[evenFst])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        numDict1 = collections.defaultdict(int)\n",
    "        oddFst = oddSnd = -1\n",
    "        for i in range(0, n, 2):\n",
    "            numDict1[nums[i]] += 1\n",
    "            if numDict1[nums[i]] > numDict1[oddFst]:\n",
    "                oddFst, oddSnd = nums[i], oddFst\n",
    "            elif numDict1[oddFst] == numDict1[nums[i]]: \n",
    "                if oddFst != nums[i]:\n",
    "                    oddSnd = nums[i] \n",
    "            elif numDict1[nums[i]] > numDict1[oddSnd]:\n",
    "                oddSnd = nums[i] \n",
    "\n",
    "        numDict2 = collections.defaultdict(int)\n",
    "        evenFst = evenSnd = -1\n",
    "        for i in range(1, n, 2):\n",
    "            numDict2[nums[i]] += 1\n",
    "            if numDict2[nums[i]] > numDict2[evenFst]:\n",
    "                evenFst, evenSnd = nums[i], evenFst\n",
    "            elif numDict2[evenFst] == numDict2[nums[i]]: \n",
    "                if evenFst != nums[i]:\n",
    "                    evenSnd = nums[i] \n",
    "            elif numDict2[nums[i]] > numDict2[evenSnd]:\n",
    "                evenSnd = nums[i] \n",
    "\n",
    "        if oddFst != evenFst:\n",
    "            return n - numDict1[oddFst] - numDict2[evenFst]\n",
    "        else:\n",
    "            return n - max(numDict1[oddFst] + numDict2[evenSnd], numDict1[oddSnd] + numDict2[evenFst])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        c1 = Counter(nums[::2])\n",
    "        c2 = Counter(nums[1::2])\n",
    "        if len(c1) < 2 and len(c2) < 2:\n",
    "            if c1.keys() == c2.keys():\n",
    "                return len(nums) >> 1\n",
    "            return 0\n",
    "        if len(c1) != 1 != len(c2):\n",
    "            (mx1, mx_c1), (sec1, sec_c1) = c1.most_common(2)\n",
    "            (mx2, mx_c2), (sec2, sec_c2) = c2.most_common(2)\n",
    "            if mx1 != mx2:\n",
    "                return len(nums) - mx_c1 - mx_c2\n",
    "            else:\n",
    "                return len(nums) - max(mx_c2 + sec_c1, mx_c1 + sec_c2)\n",
    "        if len(c2) == 1:\n",
    "            c1, c2 = c2, c1 # 确保c1长度为1，c2长度为2\n",
    "        mx1, mx_c1 = c1.most_common(1)[0]\n",
    "        (mx2, mx_c2), (sec2, sec_c2) = c2.most_common(2)\n",
    "        if mx1 != mx2:\n",
    "            return len(nums) - mx_c1 - mx_c2\n",
    "        else:\n",
    "            return len(nums) - mx_c1 - sec_c2\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        elif n == 2:\n",
    "            if nums[0] == nums[1]:\n",
    "                return 1\n",
    "            return 0\n",
    "\n",
    "        even = Counter(nums[::2])\n",
    "        odd = Counter(nums[1::2])\n",
    "        if len(even) == 1:\n",
    "            even[-1] = 0\n",
    "        if len(odd) == 1:\n",
    "            odd[-2] = 0\n",
    "\n",
    "        even_max = [-1, -1]\n",
    "        for k in even:\n",
    "            if even[k] >= even[even_max[0]]:\n",
    "                even_max[1] = even_max[0]\n",
    "                even_max[0] = k\n",
    "            elif even[k] > even[even_max[1]]:\n",
    "                even_max[1] = k\n",
    "\n",
    "        odd_max = [-2, -2]             \n",
    "        for k in odd:\n",
    "            if odd[k] >= odd[odd_max[0]]:\n",
    "                odd_max[1] = odd_max[0]\n",
    "                odd_max[0] = k\n",
    "            elif odd[k] > odd[odd_max[1]]:\n",
    "                odd_max[1] = k\n",
    "\n",
    "        if even_max[0] != odd_max[0]:\n",
    "            return n - even[even_max[0]] - odd[odd_max[0]]\n",
    "        else:\n",
    "            p1 = even[even_max[0]] + odd[odd_max[1]]\n",
    "            p2 = even[even_max[1]] + odd[odd_max[0]]  \n",
    "            return n - max(p1, p2)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        if length < 2: return 0\n",
    "        n1 = [nums[i] for i in range(0, length, 2)]\n",
    "        n2 = [nums[i] for i in range(1, length, 2)]\n",
    "        count1, count2 = {}, {}\n",
    "        for i in n1:\n",
    "            if count1.get(i):\n",
    "                count1[i] += 1\n",
    "            else:\n",
    "                count1[i] = 1\n",
    "        for i in n2:\n",
    "            if count2.get(i):\n",
    "                count2[i] += 1\n",
    "            else:\n",
    "                count2[i] = 1\n",
    "        recount1 = {v:k for k,v in count1.items()}\n",
    "        recount2 = {v:k for k,v in count2.items()}\n",
    "        val1 = list(count1.values())\n",
    "        val2 = list(count2.values())\n",
    "        val1.sort()\n",
    "        val2.sort()\n",
    "        res = 0\n",
    "        # print(count1, count2)\n",
    "        # print(length, val1, val2)\n",
    "        a, b = val1[-1], val2[-1]\n",
    "        c, d = 0, 0\n",
    "        if len(val1)>1: c = val1[-2]\n",
    "        if len(val2)>1: d = val2[-2]\n",
    "        if recount1.get(val1[-1]) == recount2.get(val2[-1]):\n",
    "            res = length - max(a+d, b+c)\n",
    "        else:\n",
    "            res = length - val1[-1] - val2[-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1: return 0\n",
    "        if n == 2: return 1 if nums[1] == nums[0] else 0\n",
    "\n",
    "        odd_dict = Counter()\n",
    "        even_dict = Counter()\n",
    "        for i, num in enumerate(nums):\n",
    "            if i % 2 == 0:\n",
    "                even_dict[num] += 1\n",
    "            else:\n",
    "                odd_dict[num] += 1\n",
    "\n",
    "        a = odd_dict.most_common(2)\n",
    "        b = even_dict.most_common(2)\n",
    "        # print(a, b)\n",
    "        if a[0][0] != b[0][0]:\n",
    "            return n - a[0][1] - b[0][1]\n",
    "        else:\n",
    "            if len(a) == 1 and len(b) == 1:\n",
    "                return min(a[0][1], b[0][1])\n",
    "            elif len(a) == 2 and len(b) == 1:\n",
    "                return n - b[0][1] - a[1][1]\n",
    "            elif len(a) == 1 and len(b) == 2:\n",
    "                return n - b[1][1] - a[0][1]\n",
    "            elif len(a) == 2 and len(b) == 2:\n",
    "                return min(n - b[1][1] - a[0][1], n - b[0][1] - a[1][1])\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        c0, c1 = Counter(), Counter()\n",
    "        for i, x in enumerate(nums):\n",
    "            if i % 2:\n",
    "                c1[x] += 1\n",
    "            else:\n",
    "                c0[x] += 1\n",
    "        c0[0], c1[0] = 0, 0\n",
    "        cm0 = c0.most_common(2)\n",
    "        cm1 = c1.most_common(2)\n",
    "        if cm0[0][0] != cm1[0][0]:\n",
    "            return n - cm0[0][1] - cm1[0][1]\n",
    "        return n - max(cm0[0][1] + cm1[1][1], cm0[1][1] + cm1[0][1])            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        a, b = 0, 0\n",
    "        c1, c2 = Counter(), Counter()\n",
    "        for i in range(n):\n",
    "            if i % 2 == 0:\n",
    "                c1[nums[i]] += 1\n",
    "                a += 1\n",
    "            else:\n",
    "                c2[nums[i]] += 1\n",
    "                b += 1\n",
    "        \n",
    "        ans = inf\n",
    "        for k1, v1 in c1.most_common(2):\n",
    "            for k2, v2 in c2.most_common(2):\n",
    "                if k1 != k2:\n",
    "                    ans = min(ans, a - v1 + b - v2)\n",
    "                else:\n",
    "                    ans = min(ans, a + b - v2, a - v1 + b)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        a, b = 0, 0\n",
    "        c1, c2 = Counter(), Counter()\n",
    "        for i in range(n):\n",
    "            if i % 2 == 0:\n",
    "                c1[nums[i]] += 1\n",
    "                a += 1\n",
    "            else:\n",
    "                c2[nums[i]] += 1\n",
    "                b += 1\n",
    "        \n",
    "        ans = inf\n",
    "        for k1, v1 in c1.most_common(2) + [(0, 0)]:\n",
    "            for k2, v2 in c2.most_common(2) + [(0, 0)]:\n",
    "                if k1 != k2:\n",
    "                    ans = min(ans, a - v1 + b - v2)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 1:\n",
    "            return 0\n",
    "        if len(nums) == 2 and nums[0] != nums[1]:\n",
    "            return 0\n",
    "        elif len(nums) == 2:\n",
    "            return 1\n",
    "        odd_map = {}\n",
    "        even_map = {}\n",
    "        even_max = 1\n",
    "        odd_max = 1\n",
    "        even = nums[0]\n",
    "        odd = nums[1]\n",
    "        \n",
    "        for i in range(0, len(nums)):\n",
    "            if i % 2 == 0:\n",
    "                if nums[i] not in even_map:\n",
    "                    even_map[nums[i]] = 0\n",
    "                even_map[nums[i]] += 1\n",
    "                if even_map[nums[i]] > even_max:\n",
    "                    even_max = even_map[nums[i]]\n",
    "                    even = nums[i]\n",
    "            else:\n",
    "                if nums[i] not in odd_map:\n",
    "                    odd_map[nums[i]] = 0\n",
    "                odd_map[nums[i]] += 1\n",
    "                if odd_map[nums[i]] > odd_max:\n",
    "                    odd_max = odd_map[nums[i]]\n",
    "                    odd = nums[i]\n",
    "        \n",
    "        if even != odd:\n",
    "            return len(nums) - even_max - odd_max\n",
    "        \n",
    "        odd_max2 = 0\n",
    "        for k in odd_map:\n",
    "            if k != odd:\n",
    "                odd_max2 = max(odd_max2, odd_map[k])\n",
    "        \n",
    "        even_max2 = 0\n",
    "        for k in even_map:\n",
    "            if k != even:\n",
    "                even_max2 = max(even_max2, even_map[k])\n",
    "        return min(len(nums) - even_max2 - odd_max, len(nums) - odd_max2 - even_max)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        def maxFrequence(l):\n",
    "            dic = collections.Counter(l)\n",
    "            return sorted([[dic[x], x] for x in dic], reverse = True)[:2]\n",
    "\n",
    "        if len(nums) <= 1:\n",
    "            return 0\n",
    "        mf1, mf2 = maxFrequence(nums[::2]), maxFrequence(nums[1::2])\n",
    "        if mf1[0][1] == mf2[0][1]:\n",
    "            if len(mf1) == 1:\n",
    "                if len(mf2) == 1:\n",
    "                    return mf2[0][0]\n",
    "                else:\n",
    "                    return len(nums) - mf1[0][0] - mf2[1][0]\n",
    "            else:\n",
    "                if len(mf2) == 1:\n",
    "                    return len(nums) - mf1[1][0] - mf2[0][0]\n",
    "                else:\n",
    "                    return min(len(nums) - mf1[0][0] - mf2[1][0], len(nums) - mf1[1][0] - mf2[0][0])\n",
    "        else:\n",
    "            return len(nums) - mf1[0][0] - mf2[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\" \n",
    "        返回最高出现和次高出现次数的键值对\n",
    "    \"\"\"\n",
    "    def get_max_pair(self, num_time_dict):\n",
    "        best_2_pair = Counter(num_time_dict).most_common(2)\n",
    "        if not best_2_pair:\n",
    "            return 0, 0, 0, 0\n",
    "        elif len(best_2_pair) == 1:\n",
    "            return *best_2_pair[0], 0, 0\n",
    "        return *best_2_pair[0], *best_2_pair[1]\n",
    "\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        # 找出奇数&偶数下标数组数据中出现次数最多的\n",
    "        num1_time_dict = {}\n",
    "        num2_time_dict = {}\n",
    "        for i in range(0, len(nums), 2):\n",
    "            if nums[i] in num1_time_dict:\n",
    "                num1_time_dict[nums[i]] += 1\n",
    "            else:\n",
    "                num1_time_dict[nums[i]] = 1\n",
    "        \n",
    "        for i in range(1, len(nums), 2):\n",
    "            if nums[i] in num2_time_dict:\n",
    "                num2_time_dict[nums[i]] += 1\n",
    "            else:\n",
    "                num2_time_dict[nums[i]] = 1\n",
    "                \n",
    "        num1_0, num1_0_time, num1_1, num1_1_time = self.get_max_pair(num1_time_dict)\n",
    "        num2_0, num2_0_time, num2_1, num2_1_time  = self.get_max_pair(num2_time_dict)\n",
    "\n",
    "        if num1_0 != num2_0:\n",
    "            return len(nums) - (num1_0_time + num2_0_time)\n",
    "\n",
    "        return len(nums) - max(num1_0_time + num2_1_time, num1_1_time + num2_0_time)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        cnt1 = Counter(nums[::2])\n",
    "        cnt2 = Counter(nums[1::2])\n",
    "        ans = 0\n",
    "        list1 = sorted(cnt1.items(), key=lambda x: -x[1])[:2]\n",
    "        list2 = sorted(cnt2.items(), key = lambda x: -x[1])[:2]\n",
    "        if len(list1):\n",
    "            ans = max(ans, list1[0][1])\n",
    "        if len(list2):\n",
    "            ans = max(ans, list2[0][1])\n",
    "        for k1, v1 in list1:\n",
    "            for k2, v2 in list2:\n",
    "                if k1 != k2:\n",
    "                    ans = max(ans, v1 + v2)\n",
    "        return len(nums) - ans\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        odd = defaultdict(int)\n",
    "        even = defaultdict(int)\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        for i in range(0, n, 2):\n",
    "            even[nums[i]] += 1\n",
    "        for i in range(1, n, 2):\n",
    "            odd[nums[i]] += 1\n",
    "        odd_item = sorted(list(odd.items()), key=lambda x: -x[1])[:2]\n",
    "        even_item = sorted(list(even.items()), key=lambda x: -x[1])[:2]\n",
    "        ans = min(n-odd_item[0][1], n-even_item[0][1])\n",
    "        for a, cnt1 in odd_item:\n",
    "            for b, cnt2 in even_item:\n",
    "                if a != b:\n",
    "                    cur = n-cnt1-cnt2\n",
    "                    ans = ans if ans < cur else cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        \n",
    "        cnt0 = Counter(nums[::2])   # 从下标0开始，间隔为2\n",
    "        cnt1 = Counter(nums[1::2])  # 从下标1开始，间隔为2\n",
    "        \n",
    "        cnt0 = sorted(cnt0.items(), key=lambda x: -x[1])    # 按照出现次数倒序排列\n",
    "        cnt1 = sorted(cnt1.items(), key=lambda x: -x[1])\n",
    "        \n",
    "        if cnt0[0][0] != cnt1[0][0]:    # 两个数组中，出现次数最多的元素不同\n",
    "            return n-cnt0[0][1]-cnt1[0][1]\n",
    "        else:                           # 两个数组中，出现次数最多的元素相同\n",
    "            cost0 = n - cnt0[0][1] - (0 if len(cnt1)==1 else cnt1[1][1])    # 保留偶数组中出现次数最多的元素，并考虑保留奇数组中出现次数第二多（如存在）的元素\n",
    "            cost1 = n - cnt1[0][1] - (0 if len(cnt0)==1 else cnt0[1][1])    # 保留奇数组中出现次数最多的元素，并考虑保留偶数组中出现次数第二多（如存在）的元素\n",
    "\n",
    "            return min(cost0, cost1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        \n",
    "        cnt0 = Counter(nums[::2])   \n",
    "        cnt1 = Counter(nums[1::2])  \n",
    "        \n",
    "        cnt0 = sorted(cnt0.items(), key=lambda x: -x[1])    \n",
    "        cnt1 = sorted(cnt1.items(), key=lambda x: -x[1])\n",
    "        \n",
    "        if cnt0[0][0] != cnt1[0][0]:   \n",
    "            return n-cnt0[0][1]-cnt1[0][1]\n",
    "        else:                           \n",
    "            cost0 = n - cnt0[0][1] - (0 if len(cnt1)==1 else cnt1[1][1])   \n",
    "            cost1 = n - cnt1[0][1] - (0 if len(cnt0)==1 else cnt0[1][1])    \n",
    "            return min(cost0, cost1)   \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        \n",
    "        cnt0 = Counter(nums[::2])\n",
    "        cnt1 = Counter(nums[1::2])\n",
    "\n",
    "        cnt0 = sorted(cnt0.items(), key=lambda x: -x[1])\n",
    "        cnt1 = sorted(cnt1.items(), key=lambda x: -x[1])\n",
    "\n",
    "        if cnt0[0][0] != cnt1[0][0]:\n",
    "            return n - cnt0[0][1] - cnt1[0][1]\n",
    "        else:\n",
    "            cost0 = n - cnt0[0][1] - (0 if len(cnt1) == 1 else cnt1[1][1])\n",
    "            cost1 = n - cnt1[0][1] - (0 if len(cnt0) == 1 else cnt0[1][1])\n",
    "            return min(cost0, cost1)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        #奇 odd 偶 even\n",
    "        n = len(nums)\n",
    "        if n ==1 : return 0\n",
    "        dic_ji = Counter([nums[i] for i in range(0,n,2)])\n",
    "        dic_ou = Counter([nums[i] for i in range(1,n,2)])\n",
    "        dic_ji = sorted(dic_ji.items(), key = lambda x: x[1], reverse = True)\n",
    "        dic_ou = sorted(dic_ou.items(), key = lambda x: x[1], reverse = True)\n",
    "        a = dic_ji[0][0]\n",
    "        c = dic_ou[0][0]\n",
    "        len1 = len(dic_ji)\n",
    "        len2 = len(dic_ou)\n",
    "        if a != c:\n",
    "            return n - dic_ji[0][1] - dic_ou[0][1]\n",
    "        elif len1 > 1 and len2 > 1:\n",
    "            return n - max(dic_ji[0][1] + dic_ou[1][1], dic_ji[1][1]+ dic_ou[0][1])\n",
    "        elif len1 == 1 and len2 == 1:\n",
    "            return n // 2 \n",
    "        elif len1 == 1 and len2 > 1:\n",
    "            return n - dic_ji[0][1] - dic_ou[1][1]\n",
    "        elif len1 > 1 and len2 == 1:\n",
    "            return n - dic_ji[1][1]- dic_ou[0][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n ==1 : return 0\n",
    "        #nums_ji = [nums[i] for i in range(0,n,2)]\n",
    "        #nums_ou = [nums[i] for i in range(1,n,2)]\n",
    "        dic_ji = Counter([nums[i] for i in range(0,n,2)])\n",
    "        dic_ou = Counter([nums[i] for i in range(1,n,2)])\n",
    "        dic_ji = sorted(dic_ji.items(), key = lambda x: x[1], reverse = True)\n",
    "        dic_ou = sorted(dic_ou.items(), key = lambda x: x[1], reverse = True)\n",
    "        #print(dic_ji,dic_ou)\n",
    "        a = dic_ji[0][0]\n",
    "        c = dic_ou[0][0]\n",
    "        len1 = len(dic_ji)\n",
    "        len2 = len(dic_ou)\n",
    "        #print(a,c)\n",
    "        if a != c:\n",
    "            return n - dic_ji[0][1] - dic_ou[0][1]\n",
    "        elif len1 > 1 and len2 > 1:\n",
    "            return n - max(dic_ji[0][1] + dic_ou[1][1], dic_ji[1][1]+ dic_ou[0][1])\n",
    "        elif len1 == 1 and len2 == 1:\n",
    "            return n // 2 \n",
    "        elif len1 == 1 and len2 > 1:\n",
    "            return n - dic_ji[0][1] - dic_ou[1][1]\n",
    "        elif len1 > 1 and len2 == 1:\n",
    "            return n - dic_ji[1][1]- dic_ou[0][1]\n",
    "        #ji = dic_ji[0][0]\n",
    "        #ou = dic_ou[0][0]\n",
    "        '''\n",
    "        if ji == ou :\n",
    "            if dic_ji[0][1] > dic_ou[0][1]:\n",
    "\n",
    "                if len(dic_ou) == 1:\n",
    "                    ou = ji-1\n",
    "                else:\n",
    "                    ou = dic_ou[1][0]\n",
    "            elif dic_ji[0][1] < dic_ou[0][1]: \n",
    "                if len(dic_ji) == 1:\n",
    "                    ji = ou-1\n",
    "                else:\n",
    "                    ji = dic_ji[1][0]\n",
    "            else:#数量 和值都相等\n",
    "                if len(dic_ji) == len(dic_ou) == 1:\n",
    "                    ji = ou-1\n",
    "                elif len(dic_ji) !=1 and len(dic_ou) != 1:\n",
    "                    if dic_ji[1][1] > dic_ou[1][1]:\n",
    "                        ji = dic_ji[1][0]\n",
    "                    else: ou = dic_ou[1][0]\n",
    "                elif len(dic_ji) ==1:\n",
    "                    ou = dic_ou[1][0]\n",
    "                else:ji = dic_ji[1][0]\n",
    "            '''\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        a = sorted(list(Counter(nums[::2]).items()),key = lambda x:-x[1])\n",
    "        b = sorted(list(Counter(nums[1::2]).items()),key = lambda x:-x[1])\n",
    "        n = len(nums)\n",
    "        if a and b:\n",
    "            if a[0][0] == b[0][0]:\n",
    "                if len(a) == len(b) == 1:\n",
    "                    return min(a[0][1],b[0][1])\n",
    "                if len(a) == 1:\n",
    "                    return n-a[0][1]-b[1][1]\n",
    "                if len(b) == 1:\n",
    "                    return n-a[1][1]-b[0][1]\n",
    "                return min(n-a[0][1]-b[1][1],n-a[1][1]-b[0][1])\n",
    "            else:\n",
    "                return n-a[0][1]-b[0][1]\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        odd = Counter(nums[1::2]).most_common()+[(0,0)]\n",
    "        even = Counter(nums[0::2]).most_common()+[(0,0)]\n",
    "        \n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        if odd[0][0]!=even[0][0]:\n",
    "            ans = n-odd[0][1]-even[0][1]\n",
    "        else:\n",
    "            ans = n-max(odd[0][1]+even[1][1], odd[1][1]+even[0][1])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        if(len(nums)==1):\n",
    "            return 0\n",
    "        nums1=[nums[i] for i in range(len(nums)) if i%2==0]\n",
    "        nums2=[nums[i] for i in range(len(nums)) if i%2!=0]\n",
    "\n",
    "        counter1=(Counter(nums1)).most_common()\n",
    "        counter2=(Counter(nums2)).most_common()\n",
    "        \n",
    "\n",
    "        len1=len(nums1)\n",
    "        len2=len(nums2)\n",
    "\n",
    "        if (counter1[0][0]!=counter2[0][0]):\n",
    "            return len1+len2-counter1[0][1]-counter2[0][1]\n",
    "        else:\n",
    "            modify_counter2=0 if len(counter2)==1 else counter2[1][1]\n",
    "            modify_counter1=0 if len(counter1)==1 else counter1[1][1]\n",
    "            return min(len1+len2-counter1[0][1]-modify_counter2,len1+len2-counter2[0][1]-modify_counter1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n ==1 : return 0\n",
    "        nums_ji = [nums[i] for i in range(0,n,2)]\n",
    "        nums_ou = [nums[i] for i in range(1,n,2)]\n",
    "        dic_ji = Counter(nums_ji)\n",
    "        dic_ou = Counter(nums_ou)\n",
    "        dic_ji = sorted(dic_ji.items(), key = lambda x: x[1], reverse = True)\n",
    "        dic_ou = sorted(dic_ou.items(), key = lambda x: x[1], reverse = True)\n",
    "        print(dic_ji,dic_ou)\n",
    "        a = dic_ji[0][0]\n",
    "        c = dic_ou[0][0]\n",
    "        print(a,c)\n",
    "        if a != c:\n",
    "            return n - dic_ji[0][1] - dic_ou[0][1]\n",
    "        elif len(dic_ji) > 1 and len(dic_ou) > 1:\n",
    "            return n - max(dic_ji[0][1] + dic_ou[1][1], dic_ji[1][1]+ dic_ou[0][1])\n",
    "        elif len(dic_ji) == 1 and len(dic_ou) == 1:\n",
    "            return n // 2 \n",
    "        elif len(dic_ji) == 1 and len(dic_ou) > 1:\n",
    "            return n - dic_ji[0][1] - dic_ou[1][1]\n",
    "        elif len(dic_ji) > 1 and len(dic_ou) == 1:\n",
    "            return n - dic_ji[1][1]- dic_ou[0][1]\n",
    "        #ji = dic_ji[0][0]\n",
    "        #ou = dic_ou[0][0]\n",
    "        '''\n",
    "        if ji == ou :\n",
    "            if dic_ji[0][1] > dic_ou[0][1]:\n",
    "\n",
    "                if len(dic_ou) == 1:\n",
    "                    ou = ji-1\n",
    "                else:\n",
    "                    ou = dic_ou[1][0]\n",
    "            elif dic_ji[0][1] < dic_ou[0][1]: \n",
    "                if len(dic_ji) == 1:\n",
    "                    ji = ou-1\n",
    "                else:\n",
    "                    ji = dic_ji[1][0]\n",
    "            else:#数量 和值都相等\n",
    "                if len(dic_ji) == len(dic_ou) == 1:\n",
    "                    ji = ou-1\n",
    "                elif len(dic_ji) !=1 and len(dic_ou) != 1:\n",
    "                    if dic_ji[1][1] > dic_ou[1][1]:\n",
    "                        ji = dic_ji[1][0]\n",
    "                    else: ou = dic_ou[1][0]\n",
    "                elif len(dic_ji) ==1:\n",
    "                    ou = dic_ou[1][0]\n",
    "                else:ji = dic_ji[1][0]\n",
    "            '''\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1: return 0\n",
    "        num1=[]\n",
    "        num2=[]\n",
    "        l=len(nums)    \n",
    "        for i in range(0,l):\n",
    "            if i%2!=0:\n",
    "                num1.append(nums[i])\n",
    "            else:\n",
    "                num2.append(nums[i])\n",
    "        c1,c2=Counter(num1),Counter(num2)\n",
    "        c1=sorted(c1.items(),key=lambda x:-x[1])\n",
    "        c2=sorted(c2.items(),key=lambda x:-x[1])\n",
    "        if c1[0][0]!=c2[0][0]:\n",
    "            return l-c1[0][1]-c2[0][1]\n",
    "        else:\n",
    "            if len(c1)<2:\n",
    "                c1.append((0,0))\n",
    "            if len(c2)<2:\n",
    "                c2.append((0,0))\n",
    "        return min(l-c1[1][1]-c2[0][1],l-c1[0][1]-c2[1][1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "\n",
    "        odd = {}\n",
    "        even = {}\n",
    "        for index, num in enumerate(nums):\n",
    "            if index % 2 == 0:\n",
    "                even[num] = even.get(num, 0) + 1\n",
    "            else:\n",
    "                odd[num] = odd.get(num, 0) + 1\n",
    "        \n",
    "        odd_info = sorted(odd.items(), key=lambda d:d[1], reverse=True)\n",
    "        even_info = sorted(even.items(), key=lambda d:d[1], reverse=True)\n",
    "        odd_cnt = n // 2\n",
    "        even_cnt = (n + 1) // 2\n",
    "\n",
    "        if odd_info[0][0] != even_info[0][0]:\n",
    "            return n - odd_info[0][1] - even_info[0][1]\n",
    "        elif len(odd_info) == 1:\n",
    "            if len(even_info) == 1:\n",
    "                return odd_cnt\n",
    "            else:\n",
    "                return even_cnt - even_info[1][1]\n",
    "        elif len(even_info) == 1:\n",
    "            return odd_cnt - odd_info[1][1]\n",
    "        else:\n",
    "            return min(n - odd_info[0][1] - even_info[1][1], n - odd_info[1][1] - even_info[0][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:\n",
    "            return 0\n",
    "\n",
    "        dict0 = {}\n",
    "        dict1 = {}\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if i%2==0:\n",
    "                if num not in dict0:\n",
    "                    dict0[num] = 1\n",
    "                else:\n",
    "                    dict0[num] +=1\n",
    "            else:\n",
    "                if num not in dict1:\n",
    "                    dict1[num] = 1\n",
    "                else:\n",
    "                    dict1[num] +=1\n",
    "        \n",
    "        a0 = sorted(dict0.items(),key = lambda x:x[1],reverse = True)\n",
    "        a1 = sorted(dict1.items(),key = lambda x:x[1],reverse = True)\n",
    "        \n",
    "\n",
    "        # 如果0和1位置上出现的key不相等\n",
    "        if a0[0][0]!=a1[0][0]:\n",
    "            return len(nums)-a0[0][1]-a1[0][1]\n",
    "\n",
    "        else:\n",
    "            # 需要先对a0, a1的长度进行判断\n",
    "            candicate1 = -inf\n",
    "            candicate0 = -inf\n",
    "            if len(a0)>1:\n",
    "                candicate0 = a0[1][1]\n",
    "            if len(a1)>1:\n",
    "                candicate1 = a1[1][1]\n",
    "            return len(nums)-max(a0[0][1]+candicate1,candicate0+a1[0][1],a0[0][1],a1[0][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1: return 0\n",
    "        cnt1 = Counter(nums[::2])\n",
    "        cnt2 = Counter(nums[1::2])\n",
    "        c1 = sorted(cnt1.items(), key=lambda x:x[1], reverse=True)\n",
    "        c2 = sorted(cnt2.items(), key=lambda x:x[1], reverse=True)\n",
    "        c1.append((0, 0))\n",
    "        c2.append((0, 0))\n",
    "        if c1[0][0] != c2[0][0]:\n",
    "            return n - c1[0][1] - c2[0][1]\n",
    "        return n - max(c1[0][1] + c2[1][1], c1[1][1] + c2[0][1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        odd, even = Counter(nums[1::2]), Counter(nums[::2])\n",
    "        a1 = sorted(odd.items(), key = lambda x: -x[1])\n",
    "        a2 = sorted(even.items(), key = lambda x: -x[1])\n",
    "        ans = 0\n",
    "        # print(f'{a1,a2}')\n",
    "        for i in range(0, min(2, len(a1))):\n",
    "            for j in range(0, min(2, len(a2))):\n",
    "                if a1[i][0] != a2[j][0]:\n",
    "                    ans = max(ans, a1[i][1] + a2[j][1])\n",
    "        return (len(nums) - ans) if ans != 0 else len(nums) // 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        \n",
    "        odd = defaultdict(int)\n",
    "        even = defaultdict(int)\n",
    "        n = len(nums)\n",
    "        odd_cnt = 0\n",
    "        even_cnt = 0\n",
    "        for i in range(n):\n",
    "            if i %2 == 0:\n",
    "                even[nums[i]] += 1\n",
    "                even_cnt += 1\n",
    "            else:\n",
    "                odd[nums[i]] += 1\n",
    "                odd_cnt += 1\n",
    "                \n",
    "                \n",
    "        \n",
    "        a = b = 0\n",
    "        for num in even:\n",
    "            if even[num] >= a:\n",
    "                a, b = even[num], a\n",
    "            elif even[num] >= b:\n",
    "                b = even[num]\n",
    "        \n",
    "        ans = odd_cnt + even_cnt - a\n",
    "        for num in odd:\n",
    "            cur = odd_cnt - odd[num]\n",
    "            if even[num] == a:\n",
    "                x = b\n",
    "            else:\n",
    "                x = a\n",
    "            cur += even_cnt - x\n",
    "            if cur < ans:\n",
    "                ans = cur\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:\n",
    "            return 0\n",
    "        if len(nums)==2:\n",
    "            if nums[1]==nums[0]:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "        oudict = dict()\n",
    "        odddict = dict()\n",
    "        for i in range(len(nums)):\n",
    "            if i%2==0:\n",
    "                if nums[i] not in oudict.keys():\n",
    "                    oudict[nums[i]]=1\n",
    "                else:\n",
    "                    oudict[nums[i]]+=1\n",
    "            else:\n",
    "                if nums[i] not in odddict.keys():\n",
    "                    odddict[nums[i]]=1\n",
    "                else:\n",
    "                    odddict[nums[i]]+=1\n",
    "        \n",
    "        newoudict = list(sorted(oudict.items(),key=lambda x:x[1]))\n",
    "        newodddict = list(sorted(odddict.items(),key=lambda x:x[1]))\n",
    "        print(\"sss\",newoudict,newodddict)\n",
    "        \n",
    "\n",
    "        a = newoudict.pop()\n",
    "        b = newodddict.pop()\n",
    "        # print(a,b)\n",
    "        if a[0] == b[0]:\n",
    "            if not newodddict and not newoudict:\n",
    "                if a[1]<=b[1]:\n",
    "                    a = (b[0]+1,1)\n",
    "                else:\n",
    "                    b = (a[0]+1,1)\n",
    "            elif not newodddict:\n",
    "                a = newoudict.pop()\n",
    "            elif not newoudict:\n",
    "                b = newodddict.pop()\n",
    "            else:\n",
    "                c = newoudict.pop()\n",
    "                d = newodddict.pop()\n",
    "                if a[1]+d[1] >= b[1]+c[1]:\n",
    "                    a = a\n",
    "                    b = d\n",
    "                else:\n",
    "                    a = c\n",
    "                    b = b\n",
    "        print(a,b)\n",
    "        cnt1 = 0\n",
    "        cnt2 = 0\n",
    "        # print(\"aaa\",a,b)\n",
    "        # print(newodddict,newoudict)\n",
    "        for i in range(len(nums)):\n",
    "            if i%2==0:\n",
    "                if nums[i] != a[0]:\n",
    "                    cnt1+=1\n",
    "            else:\n",
    "                if nums[i] != b[0]:\n",
    "                    cnt2+=1\n",
    "        return cnt1+cnt2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        odds, even = nums[::2], nums[1::2]\n",
    "        c_o, c_e = Counter(odds), Counter(even)\n",
    "        l_o, l_e = list(c_o.items()), list(c_e.items())\n",
    "        l_o.sort(key=lambda x:x[1], reverse=True)\n",
    "        l_e.sort(key=lambda x:x[1], reverse=True)\n",
    "        l_o.append([-1, 0])  # 哨兵\n",
    "        l_e.append([-1, 0])  # 哨兵\n",
    "        if l_e[0][0] != l_o[0][0]:\n",
    "            return n - l_e[0][1] - l_o[0][1]\n",
    "        return min(n - l_e[0][1] - l_o[1][1], n - l_e[1][1] - l_o[0][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if(n <= 1):\n",
    "            return 0\n",
    "        mp1 = {}\n",
    "        mp2 = {}\n",
    "        cnt1 = 0\n",
    "        cnt2 = 0\n",
    "        for i in range(n):\n",
    "            if(i % 2 == 0):\n",
    "                if(nums[i] not in mp1):\n",
    "                    mp1[nums[i]] = 1\n",
    "                else:\n",
    "                    mp1[nums[i]] += 1\n",
    "                cnt1 += 1\n",
    "            else:\n",
    "                if(nums[i] not in mp2):\n",
    "                    mp2[nums[i]] = 1\n",
    "                else:\n",
    "                    mp2[nums[i]] += 1       \n",
    "                cnt2 += 1  \n",
    "        heap1 = []\n",
    "        for k1, v1 in mp1.items():\n",
    "            heapq.heappush(heap1,[-v1,k1])\n",
    "        heap2 = []\n",
    "        for k2, v2 in mp2.items():\n",
    "            heapq.heappush(heap2,[-v2,k2])\n",
    "        if(heap1[0][1] != heap2[0][1]):\n",
    "            return cnt1 + heap1[0][0] + cnt2 + heap2[0][0]\n",
    "        else:\n",
    "            if(len(heap1) == 1 and len(heap2) == 1):\n",
    "                return min(cnt1, cnt2)\n",
    "            elif(len(heap1) == 1):\n",
    "                v21, k21 = heapq.heappop(heap2)\n",
    "                v22, k22 = heapq.heappop(heap2)\n",
    "                return min(cnt1 + cnt2 + v21, cnt2 + v22)\n",
    "            elif(len(heap2) == 1):\n",
    "                v11, k11 = heapq.heappop(heap1)\n",
    "                v12, k12 = heapq.heappop(heap1)\n",
    "                return min(cnt2 + cnt1 + v11, cnt1 + v12)     \n",
    "            else:\n",
    "                v11, k11 = heapq.heappop(heap1)\n",
    "                v12, k12 = heapq.heappop(heap1)\n",
    "                v21, k21 = heapq.heappop(heap2)\n",
    "                v22, k22 = heapq.heappop(heap2)\n",
    "                return min(cnt1+v11+cnt2+v22, cnt1+v12+cnt2+v21) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if(n <= 1):\n",
    "            return 0\n",
    "        mp1 = {}\n",
    "        mp2 = {}\n",
    "        cnt1 = 0\n",
    "        cnt2 = 0\n",
    "        for i in range(n):\n",
    "            if(i % 2 == 0):\n",
    "                if(nums[i] not in mp1):\n",
    "                    mp1[nums[i]] = 1\n",
    "                else:\n",
    "                    mp1[nums[i]] += 1\n",
    "                cnt1 += 1\n",
    "            else:\n",
    "                if(nums[i] not in mp2):\n",
    "                    mp2[nums[i]] = 1\n",
    "                else:\n",
    "                    mp2[nums[i]] += 1       \n",
    "                cnt2 += 1  \n",
    "        heap1 = []\n",
    "        for k1, v1 in mp1.items():\n",
    "            heapq.heappush(heap1,[-v1,k1])\n",
    "        heap2 = []\n",
    "        for k2, v2 in mp2.items():\n",
    "            heapq.heappush(heap2,[-v2,k2])\n",
    "        if(heap1[0][1] != heap2[0][1]):\n",
    "            return cnt1 + heap1[0][0] + cnt2 + heap2[0][0]\n",
    "        else:\n",
    "            if(len(heap1) == 1 and len(heap2) == 1):\n",
    "                return min(cnt1, cnt2)\n",
    "            elif(len(heap1) == 1):\n",
    "                v21, k21 = heapq.heappop(heap2)\n",
    "                v22, k22 = heapq.heappop(heap2)\n",
    "                return min(cnt1 + cnt2 + v21, cnt2 + v22)\n",
    "            elif(len(heap2) == 1):\n",
    "                v11, k11 = heapq.heappop(heap1)\n",
    "                v12, k12 = heapq.heappop(heap1)\n",
    "                return min(cnt2 + cnt1 + v11, cnt1 + v12)     \n",
    "            else:\n",
    "                v11, k11 = heapq.heappop(heap1)\n",
    "                v12, k12 = heapq.heappop(heap1)\n",
    "                v21, k21 = heapq.heappop(heap2)\n",
    "                v22, k22 = heapq.heappop(heap2)\n",
    "                return min(cnt1+v11+cnt2+v22, cnt1+v12+cnt2+v21) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        if len(nums)<=1:\n",
    "            return 0\n",
    "        num1 = nums[0::2]\n",
    "        num2 = nums[1::2]\n",
    "\n",
    "        C1 = Counter(num1)\n",
    "        C2 = Counter(num2)\n",
    "\n",
    "        item1 = list(sorted(C1.items(),key = lambda x:x[1], reverse = True))\n",
    "        item2 = list(sorted(C2.items(),key = lambda x:x[1], reverse = True))\n",
    "\n",
    "        k1_1st = item1[0][0]\n",
    "        v1_1st = item1[0][1]\n",
    "\n",
    "        k2_1st = item2[0][0]\n",
    "        v2_1st = item2[0][1]\n",
    "\n",
    "        if k1_1st != k2_1st:\n",
    "            return len(nums) - v1_1st - v2_1st\n",
    "        else:\n",
    "            if len(item1)==1 and len(item2)==1:\n",
    "                return v2_1st\n",
    "            elif len(item1)==1:\n",
    "                v2_2nd = item2[1][1]\n",
    "                return len(nums) - v1_1st - v2_2nd\n",
    "            elif len(item2)==1:\n",
    "                v1_2nd = item1[1][1]\n",
    "                return len(nums) - v1_2nd - v2_1st\n",
    "            else:\n",
    "                k1_2nd = item1[1][0] \n",
    "                v1_2nd = item1[1][1] \n",
    "                k2_2nd = item2[1][0] \n",
    "                v2_2nd = item2[1][1] \n",
    "\n",
    "                #print(k1_2nd, v1_2nd, k2_2nd, v2_2nd)\n",
    "                c_words = min(len(nums) - v1_1st - v2_2nd, len(nums) - v1_2nd - v2_1st)\n",
    "                return c_words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if(n <= 1):\n",
    "            return 0\n",
    "        mp1 = {}\n",
    "        mp2 = {}\n",
    "        cnt1 = 0\n",
    "        cnt2 = 0\n",
    "        for i in range(n):\n",
    "            if(i % 2 == 0):\n",
    "                if(nums[i] not in mp1):\n",
    "                    mp1[nums[i]] = 1\n",
    "                else:\n",
    "                    mp1[nums[i]] += 1\n",
    "                cnt1 += 1\n",
    "            else:\n",
    "                if(nums[i] not in mp2):\n",
    "                    mp2[nums[i]] = 1\n",
    "                else:\n",
    "                    mp2[nums[i]] += 1       \n",
    "                cnt2 += 1  \n",
    "        heap1 = []\n",
    "        for k1, v1 in mp1.items():\n",
    "            heapq.heappush(heap1,[-v1,k1])\n",
    "        heap2 = []\n",
    "        for k2, v2 in mp2.items():\n",
    "            heapq.heappush(heap2,[-v2,k2])\n",
    "        if(heap1[0][1] != heap2[0][1]):\n",
    "            return cnt1 + heap1[0][0] + cnt2 + heap2[0][0]\n",
    "        else:\n",
    "            if(len(heap1) == 1 and len(heap2) == 1):\n",
    "                return min(cnt1, cnt2)\n",
    "            elif(len(heap1) == 1):\n",
    "                v21, k21 = heapq.heappop(heap2)\n",
    "                v22, k22 = heapq.heappop(heap2)\n",
    "                return min(cnt1 + cnt2 + v21, cnt2 + v22)\n",
    "            elif(len(heap2) == 1):\n",
    "                v11, k11 = heapq.heappop(heap1)\n",
    "                v12, k12 = heapq.heappop(heap1)\n",
    "                return min(cnt2 + cnt1 + v11, cnt1 + v12)     \n",
    "            else:\n",
    "                v11, k11 = heapq.heappop(heap1)\n",
    "                v12, k12 = heapq.heappop(heap1)\n",
    "                v21, k21 = heapq.heappop(heap2)\n",
    "                v22, k22 = heapq.heappop(heap2)\n",
    "                return min(cnt1+v11+cnt2+v22, cnt1+v12+cnt2+v21) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter \n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return 0\n",
    "        num1, num2 = [], []\n",
    "        for i, num in enumerate(nums):\n",
    "            if i % 2 == 0:\n",
    "                num1.append(num)\n",
    "            else:\n",
    "                num2.append(num)\n",
    "\n",
    "        num1_map = Counter(num1)\n",
    "        num2_map = Counter(num2)\n",
    "        list1 = sorted(num1_map.items(), key=lambda x:x[1], reverse=True)\n",
    "        list2 = sorted(num2_map.items(), key=lambda x:x[1], reverse=True)\n",
    "        if list1[0][0] != list2[0][0]:\n",
    "            return len(nums) - list1[0][1] - list2[0][1]\n",
    "        else:\n",
    "            if len(list1)<2:\n",
    "                list1.append((0,0))\n",
    "            if len(list2)<2:\n",
    "                list2.append((0,0))\n",
    "            return min(len(nums)-list1[0][1]-list2[1][1], len(nums)-list1[1][1]-list2[0][1])\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "\n",
    "        m = [Counter(), Counter()]\n",
    "        for i in range(n):\n",
    "            m[i & 1][nums[i]] += 1\n",
    "        maxv = [(v, k) for k, v in m[0].items()]\n",
    "        maxv2 = [(v, k) for k, v in m[1].items()]\n",
    "        maxv.sort(reverse=True)\n",
    "        maxv2.sort(reverse=True)\n",
    "        if maxv[0][1] != maxv2[0][1]:\n",
    "            return n - maxv[0][0] - maxv2[0][0]\n",
    "        return  n - max(maxv[0][0] + (maxv2[1][0] if len(maxv2) > 1 else 0), (maxv[1][0] if len(maxv) > 1 else 0) + maxv2[0][0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:return 0\n",
    "        # if len(nums) == 2:return 0 if nums[0] != nums[1] else 1\n",
    "        # if len(list(Counter(nums).keys())) == 1:\n",
    "        #     return len(nums)//2\n",
    "        n = len(nums)\n",
    "        if n % 2:odd = n//2;even = n-n//2\n",
    "        else:odd = even = n//2\n",
    "        mn = inf\n",
    "        Cod = Counter()\n",
    "        Cev = Counter()\n",
    "        for idx,i in enumerate(nums):\n",
    "            if idx % 2:Cod[i] += 1\n",
    "            else:Cev[i] += 1\n",
    "        qev = []\n",
    "        qod = []\n",
    "        for idx,v in Cev.items():\n",
    "            heappush(qev,(even-v,idx))\n",
    "        for idx,v in Cod.items():\n",
    "            heappush(qod,(odd-v,idx))\n",
    "        for i in Cod.keys():\n",
    "            if qev[0][1] == i:\n",
    "                out = heappop(qev)\n",
    "                add = qev[0][0] if qev else even\n",
    "                heappush(qev,out)\n",
    "            else:\n",
    "                add = qev[0][0]\n",
    "            mn = min(mn,add+odd-Cod[i])\n",
    "        for i in Cev.keys():\n",
    "            if qod[0][1] == i:\n",
    "                out = heappop(qod)\n",
    "                add = qod[0][0] if qod else odd\n",
    "                heappush(qod,out)\n",
    "            else:\n",
    "                add = qod[0][0]\n",
    "            mn = min(mn,add+even-Cev[i])\n",
    "        return mn"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
